package 动态规划;

import java.util.*;

/**
 * 升级版3
 *  给定一颗二叉树 二叉树 取数只能取 父节点中的数据或者子节点的数据
 *  求这颗二叉树能取到的最大值
 *
 * 思路：
 *  假设二叉树 是tree，根节点是root，这棵树能取到的最大值为f(root)
 *      f(root):也无法直接得出答案， 但如果你能给出 选择f(root.child)和不选择f(root.child)的最大值.
 *  那么我就可以通过比较 选择f(root.child) 和 不选择 f(root.child)+root.data。来确定f(root)的最大值
 *       f(child):也无法直接得出答案， 但如果你能给出 选择f(child.child)和不选择f(child.child)的最大值.
 *  那么我就可以通过比较 选择f(child.child) 和 不选择 f(child.child)+child.data。来确定f(child)的最大值
 *      f(...)...
 *      直到f(null)时:不需要知道 f(null)的子节点了，因为f(null)的最大值是0
 */
public class Ch05_打家劫舍版本3 {
    public static void main(String[] args) {
        Tree<Integer> leaf1=new Tree<>(1,null,null);
        Tree<Integer> leaf2=new Tree<>(2,null,null);
        Tree<Integer> leaf3=new Tree<>(20,null,null);
        Tree<Integer> leaf4=new Tree<>(9,null,null);
        Tree<Integer> branch1=new Tree<>(8,leaf1,null);
        Tree<Integer> branch2=new Tree<>(3,leaf2,leaf3);
        Tree<Integer> branch3=new Tree<>(4,branch1,leaf4);
        Tree<Integer> branch4=new Tree<>(2,null,branch2);
        Tree<Integer> root=new Tree<>(20,branch3,branch4);
        前序(root);
        System.out.println();
        System.out.println("------------");
        中序(root);
        System.out.println();
        System.out.println("------------");
        layer(root);
        int maxTree = maxTree(root);
        System.out.println(maxTree);
    }
    static Map<Tree,Integer> map=new HashMap<>();
    /**
     * 返回 tree能取到的最大值
     * @param tree:树
     * @return
     */
    public static int maxTree(Tree<Integer> tree){
        if (map.containsKey(tree)){
            return map.get(tree);
        }
         if (tree==null){
            return 0;
        }
        int selectCurr = noSelect(tree.left)+noSelect(tree.right)+tree.data;    //选中当前节点就不能选择子节点了
//        int selectCurr =select(tree);    //选中当前节点就不能选择子节点了
        int noSelectCurr = noSelect(tree);    //不选择当前节点，那么子节点一定是被选择的
//        int noSelectCurr = select(tree.left)+select(tree.right);    //不选择当前节点，那么子节点一定是被选择的
        int max = Math.max(selectCurr, noSelectCurr);
        map.put(tree,max);
        return max;
    }

    /**
     * 返回选中当前节点的的最大值
     * @param tree:当前节点
     * @return
     */
    public static int select(Tree<Integer> tree){
        if (tree==null){
            return 0;
        }

//        int selectCurr = noSelect(tree.left)+noSelect(tree.right)+tree.data;    //选中当前节点就不能选择子节点了
//        int noSelectCurr = maxTree(tree.left)+maxTree(tree.right);
//        return Math.max(selectCurr, noSelectCurr);
        return maxTree(tree);
    }

    /**
     * 返回不选择当前节点的最大值
     * @param tree
     * @return
     */
    public static int noSelect(Tree<Integer> tree){
        if (tree==null){
            return 0;
        }
        int selectChild=maxTree(tree.left)+maxTree(tree.right);
         return selectChild;
    }

    /**
     * 层序遍历二叉树，方便查看二叉树，与题目无关
     * @param root:数的根
     */
    public static void layer(Tree root){
        Queue<Tree> queue =new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            Tree head=queue.poll();
            System.out.print(head.data+"\t");
            if (head.left!=null) {
                queue.offer(head.left);
            }
            if (head.right!=null){
                queue.offer(head.right);
            }
        }
    }

    //栈解决(迭代方式1) 前序
    public static void 前序(Tree tree) {
        Stack<Tree> data=new Stack<Tree>();
        while(tree!=null||!data.empty()) {
            if(tree!=null) {
                System.out.print(tree.data+"\t");
                data.push(tree);
                tree=tree.left;
            }else {
                tree=data.pop();
                tree=tree.right;
            }
        }
    }

    //栈解决(迭代方式1)
    public static void 中序(Tree tree) {
        Stack<Tree>data=new Stack();
        while(tree!=null||!data.empty()) {
            if(tree!=null) {
                data.push(tree);
                tree=tree.left;
            }else {
                tree=data.pop();
                System.out.print(tree.data+"\t");
                tree=tree.right;
            }
        }
    }
}
